package chapter03;

import java.util.ArrayList;
import java.util.List;

public class PathSum113 {
    /**
     * 回溯法
     * 思路和112 但本题需要回溯
     * process(x, sum, target,path) 来到x节点 之前路径上值之和为target 之前路径上节点值放在了path
     * 递归终点：
     *  1).x.left==null&&x.right==null
     *      path.add(x.val) 将当前节点加入路径
     *     if (sum+x.val)==tartget
     *          res.add(new ArrayList<>(path))
     *      return
     *  2).其他情况
     *      path.add(x.val) 将当前节点加入路径
     *      if x.left=null
     *          process(x.left,sum+x.val,tartget,path);
     *          path.remove(path.size()-1)  去掉下x.left.vale以便回溯
     *      if x.right=null
     *          process(x.right,sum+x.val,tartget,path);
     *          path.remove(path.size()-1)  去掉下x.right.vale以便回溯
     */
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
   }

    List<List<Integer>> res;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        res=new ArrayList<>();
        if(root==null){
            return res;
        }
        process(root,0,targetSum,new ArrayList<>());
        return res;
    }

    public void process(TreeNode x, int sum, int tartget,List<Integer> path){
        if(x.left==null&&x.right==null){
            path.add(x.val);
            if((sum+x.val)==tartget){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        path.add(x.val);
        if(x.left!=null){
            process(x.left,sum+x.val,tartget,path);
            path.remove(path.size()-1);
        }
        if(x.right!=null){
            process(x.right,sum+x.val,tartget,path);
            path.remove(path.size()-1);
        }
    }

    //解法2
    public List<List<Integer>> pathSum1(TreeNode root, int targetSum) {
        res=new ArrayList<>();
        if(root==null){
            return res;
        }
        List<Integer> path=new ArrayList<>();
        path.add(root.val);
        process1(root,root.val,targetSum,path);
        return res;
    }

    public void process1(TreeNode x, int sum, int tartget,List<Integer> path){
        if(x.left==null&&x.right==null){
            if(sum==tartget){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        if(x.left!=null){
            path.add(x.val);
            process1(x.left,sum+x.val,tartget,path);
            path.remove(path.size()-1);
        }
        if(x.right!=null){
            path.add(x.val);
            process1(x.right,sum+x.val,tartget,path);
            path.remove(path.size()-1);
        }
    }
}
